from topo import topo
from vmp import vm
from host import hosts
import random
from time import clock

class sortValue:
    def __init__(self):
        self.value = 0.0
        self.index = 0
    def setvalue(self, v, i):
        self.value = v
        self.index = i

def cmp(x, y):
    if x.value < y.value:
        return 1
    if x.value == y.value:
        return 0
    else:
        return -1

class sortPair:
    def __init__(self):
        self.cand1 = -1
        self.center = -1
        self.cand2 = -1
        self.value = -1

def comp(x, y):
    if x.value < y.value:
        return 1
    if x.value == y.value:
        return 0
    else:
        return -1

class swaper:
    def __init__(self):
        self.vms = vm()
        self.hosts = hosts()
        self.limit = 0
        self.focus = 0
        self.vmlist = []
        self.adjust = 0
        self.centered = {}
        self.moved = []
        self.randl = 11
        self.current_index = 0
        self.sum = 99999999999
    def load(self, topof, hostf, vmf):
        #print 'begins'
        self.vms.load(vmf)
        #print 'vms loaded'
        self.hosts.load(hostf, topof)
        #print 'hosts loaded'
        #self.vms.partition(0)
    def set(self, limit, focus):
        #print 'set'
        #tick = raw_input('[getchar]')
        self.limit = limit
        self.focus = focus
        self.vms.partition()
    def rand_place(self, fplace):
        outplace = open(fplace, 'w')
        sum = []
        for isum in self.hosts.h2slot.keys():
            #print isum
            for times in range(self.hosts.h2slot[isum]):
                sum.append(isum)
        #print 'sum',
        #print sum
        random.shuffle(sum)
        #print 'shuffled',
        #print sum
        vmpl = {}
        iter = 0
        for vm in self.vms.vms:
            vmpl[vm] = sum[iter]
            iter = iter + 1
            outplace.write(str(vm) + ' ' + str(vmpl[vm]) + '\n')
        outplace.close()
    def place(self, fplace):
        inplace = open(fplace, 'r')
        placelines = inplace.readlines()
        for pline in placelines:
            tricell = pline.split()
            #print tricell
            if len(tricell) == 2:
                #print tricell[0], tricell[1]
                self.hosts.place(int(tricell[0]), int(tricell[1]))
        #print self.hosts.v2h
        #print 'all vm placed'
    def cflow(self, v, vlist):
        sum = 0.0
        dsum = 0.0
        for vs in self.vms.vms:
            if vs != v:
                pick = self.vms.matrix[v][vs]
                dsum = dsum + pick
                sum = sum + pick * self.hosts.distance(v, vs)
                pick = self.vms.matrix[vs][v]
                dsum = dsum + pick
                sum = sum + pick * self.hosts.distance(v, vs)
        if dsum == 0:
            return 999999999
        #return 1 / dsum
        return sum / dsum / dsum
    def cal(self, i_partition):
        res = []
        for svm in self.vms.vms:
            #print svm, i_partition
            vlist = self.vms.ptree.getCluster(svm, i_partition).list
            #print vlist
            if len(vlist) < 2:
                sv = sortValue()
                sv.index = svm
                sv.value = 0
                res.append(sv)
                continue
            cf = self.cflow(svm, vlist)
            sv = sortValue()
            sv.index = svm
            sv.value = cf
            res.append(sv)
        res.sort(cmp)
        self.vmlist = res
    def pickout(self, i_partition, cent = -1):
        #print '\n\tpick from', self.vms.ptree.new_comer[i_partition]
        #print clock()
        res = []
        candidates = []
        self.cal(i_partition)
        subvmlist = []
        dellist = []
        #print
        #print self.vms.ptree.new_comer[i_partition]
        for del_vm in self.vmlist:
            if not del_vm.index in self.vms.ptree.new_comer[i_partition]:
                #print 'del', del_vm.index
                subvmlist.append(del_vm)
        if cent == -1:
            kcent = -1
            for i in range(len(self.vmlist) - 1, -1, -1):
                if kcent != -1:
                    break
                center = self.vmlist[i].index
                #if i_partition != self.vms.grouplevel and
                if  (not center in self.vms.ptree.new_comer[i_partition]):
                    continue
                #print '\tcenter', center,
                for j in range(0, len(self.vmlist), 1):
                    if j >= i:
                        break
                    cand1 = self.vmlist[j].index
                    if cand1 == center:
                        break
                    if cand1 in self.moved:
                        continue
                    if cand1 in self.vms.ptree.new_comer[i_partition]:
                        #print 'cand1', cand1,
                        d1 = self.hosts.distance(cand1, center)
                        for k in range(0, len(subvmlist), 1):
                            if k >= i:
                                break
                            cand2 = subvmlist[k].index
                            if cand2 == center or cand2 == cand1:
                                continue
#                            if (cand2, self.vms.ptree.getClusterCenter(cand2, i_partition)) in self.moved:
#                                continue
                            if cand2 in self.moved:
                                continue
                            if not cand2 in self.vms.ptree.new_comer[i_partition]:
                                d2 = self.hosts.distance(cand2, center)
                                if d1 > d2:
                                    #print 'cand2', cand2
                                    kcent = center
                                    new_enter = sortPair()
                                    new_enter.cand1 = cand1
                                    new_enter.cand2 = cand2
                                    new_enter.center = center
                                    #print self.vms.ptree.getClusterCenter(cand2, i_partition)
#                                    sum = 0.0
#                                    if self.vms.matrix.has_key(cand1):
#                                        sum = sum + self.vms.matrix[cand1].get(center, 0)
#                                    if self.vms.matrix.has_key(center):
#                                        sum = sum + self.vms.matrix[center].get(cand1, 0)
                                    new_enter.value = 1 / self.vmlist[j].value#(self.vms.matrix[center][cand1] + self.vms.matrix[cand1][center]) * (d1 - d2)
                                    candidates.append(new_enter)
            #print 'paced all', len(candidates),
            #print clock()
            lvoid = [-1, -1, -1]
            if len(candidates) > 0:
                #print 'found candidates',
                candidates.sort(comp)
#                for cand in candidates:
#                    print cand.value
                lvoid[0] = candidates[0].cand1
                lvoid[1] = candidates[0].cand2
                lvoid[2] = candidates[0].center
                #print lvoid
                self.moved.append(lvoid[0])
                #self.moved.append(lvoid[1])
#                print '\t', lvoid[0], 'to moved'
                self.vms.ptree.labelCluster(lvoid[2])
#                print '\tnew center', lvoid
            return lvoid
        else:
            center = cent
            if not cent in self.vms.ptree.new_comer[i_partition]:
                return [-1, -1, -1]
            for j in range(0, len(self.vmlist), 1):
                cand1 = self.vmlist[j].index
                if cand1 == center:
                    continue
                if cand1 in self.moved:
                    continue
                if cand1 in self.vms.ptree.new_comer[i_partition]:
                    for k in range(0, len(subvmlist), 1):
                        cand2 = subvmlist[k].index
                        if cand2 == center or cand2 == cand1:
                            continue
                        if cand2 in self.moved:
                            continue
                        if not cand2 in self.vms.ptree.new_comer[i_partition]:
                                d1 = self.hosts.distance(cand1, center)
                                d2 = self.hosts.distance(cand2, center)
                                if self.hosts.distance(cand1, center) > self.hosts.distance(cand2, center):
                                    new_enter = sortPair()
                                    new_enter.cand1 = cand1
                                    new_enter.cand2 = cand2
                                    new_enter.center = center
                                    new_enter.value = (self.vms.matrix[center][cand1] + self.vms.matrix[cand1][center]) * (d1 - d2)
                                    candidates.append(new_enter)
            lvoid = [-1, -1, -1]
            #print 'lvoid',
            if len(candidates) > 0:
                candidates.sort(comp)
                lvoid[0] = candidates[0].cand1
                lvoid[1] = candidates[0].cand2
                lvoid[2] = candidates[0].center
                print lvoid
                self.moved.append(lvoid[0])
                #self.moved.append(lvoid[1])
#                print '\t', lvoid[0], 'to moved'
                self.vms.ptree.labelCluster(lvoid[2])
#                print '\told center', lvoid
            return lvoid
    def swapij(self, i, j, cent = -1):
        #print 'swap',
        #print i, j, cent
        hosti = self.hosts.v2h[i]
        hostj = self.hosts.v2h[j]
        self.hosts.remove(i, hosti)
        self.hosts.remove(j, hostj)
        self.hosts.place(i, hostj)
        self.hosts.place(j, hosti)
    def adjustvm(self):
        self.grouplevel = -1
        swaplimit = self.limit
        level_max = len(self.vms.ptree.nodemap)
        #print swaplimit
        level = 1
        center = -1
        picked = True
        #self.adjust = 0
        testindex = self.current_index
        #print testindex, self.current_index
        #print range(testindex, len(self.vms.sortlist))
        for levelindex in range(testindex, len(self.vms.sortlist)):
            level = self.vms.sortlist[levelindex].index
#           print 'level', level
            if levelindex != testindex:
                self.moved = []
            if level == 0:
                continue
            center = -1
            while True:
                if self.adjust >= swaplimit:
                    #print levelindex
                    self.current_index = levelindex
                    return
                if picked and self.vms.ptree.cluster_occupy.has_key(level):
                    center = self.vms.ptree.cluster_occupy[level]
#                print '', 'cluster', self.vms.ptree.new_comer[level]
#                print '\tcenter', center
#                print '\tmoved', self.moved
                if center == -1:
                    pickres = self.pickout(level)
                    center = pickres[2]
                else:
                    pickres = self.pickout(level, center)
                    center = pickres[2]
                if pickres[0] != -1:
                    #print 'level', level
                    self.swapij(pickres[0], pickres[1], pickres[2])
                    psum = self.csum()
                    if psum > self.sum:
                        self.swapij(pickres[0], pickres[1], pickres[2])
                    else:
                        self.sum = psum
                        self.adjust = self.adjust + 1
                    #print self.adjust,
                    #self.test()
                else:
                    picked = False
                    if pickres[2] == -1:
                        picked = True
                        break
                        #print 'level ' + str(level) + ' not found'
                    else:
                        center = -1
                center = -1
    def outputvm(self):
        for key, value in self.hosts.v2h.items():
            print str(key) + ':' + str(value) + '  ',
        print
    def test(self):
        #print 'Test obj function:',
        sum = 0
        dsum = 0
        for ivm in self.vms.vms:
            #if self.vms.matrix.has_key(ivm):
            for jvm in self.vms.vms:
                dist = self.hosts.distance(ivm, jvm)
                sum = sum + self.vms.matrix[ivm][jvm] * dist
                dsum = dsum + self.vms.matrix[ivm][jvm]
        print sum
        return sum
    def csum(self):
        #print 'Test obj function:',
        sum = 0
        #dsum = 0
        for ivm in self.vms.vms:
            for jvm in self.vms.vms:
                dist = self.hosts.distance(ivm, jvm)
                sum = sum + self.vms.matrix[ivm][jvm] * dist
                #dsum = dsum + self.vms.matrix[ivm][jvm]
        return sum
#swap_instance = swaper()
#swap_instance.load('../topo.in', '../host.in', '../vm.in')
#swap_instance.set(10000, 1)
#swap_instance.rand_place('place.in')
#swap_instance.place('place.in')
#swap_instance.adjustvm()
#swap_instance.outputvm()
#swap_instance.test()
#swap_instance.vms.output()
#swap_instance.test()
#for i in range(1000):
    #print i,
    #swap_instance.place('place.in')
    #swap_instance.vms.changeFocus(i)
    #swap_instance.limit = i
    #swap_instance.adjustvm()
    #swap_instance.outputvm()
    #swap_instance.test()
    #swap_instance.hosts.clear()